#pragma once

#include <iostream>
#include <algorithm>
using namespace std;

template<class K>
class BSTreeNode
{
public:
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;

public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* prev = nullptr;
		Node* cur = _root;
		while (cur != nullptr) // 找到要插入的位置
		{
			if (key < cur->_key) // 要插入的值比当前值小
			{
				prev = cur; // 记录cur，等下cur更新就是cur的父亲
				cur = cur->_left; // 到左边插入
			}
			else if (key > cur->_key)
			{
				prev = cur;
				cur = cur->_right;
			}
			else
			{
				return false; // 相等，插入失败
			}
		}

		cur = new Node(key); // 走到这，cur就是要插入的位置
		if (key < prev->_key) // 如果key比cur的父亲小
		{
			prev->_left = cur; // 插入到父亲的左孩子
		}
		else
		{
			prev->_right = cur;
		}
		return true;
	}

	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* father = nullptr;
		while (cur) // 找到要删除的结点
		{
			if (key < cur->_key)
			{
				father = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				father = cur;
				cur = cur->_right;
			}
			else // 找到后开始删除，分三种情况
			{
				if (cur->_left == nullptr) // ①该结点无左孩子
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == father->_left)
						{
							father->_left = cur->_right;
						}
						else //(cur == father->_right)
						{
							father->_right = cur->_right;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else if (cur->_right == nullptr) //  ②该结点无右孩子
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == father->_left)
						{
							father->_left = cur->_left;
						}
						else //(cur == father->_left)
						{
							father->_right = cur->_left;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else // ③有两个结点，替换法删除
				{
					Node* MinNode = cur->_right;
					Node* MinParNode = cur;
					while (MinNode->_left) // 找右子树的最小
					{
						MinParNode = MinNode;
						MinNode = MinNode->_left;
					}
					swap(cur->_key, MinNode->_key); // 找到后交换

					if(MinParNode->_right == MinNode) // 链接父亲结点，这步易漏
					{
						MinParNode->_right = MinNode->_right;
					}
					else
					{
						MinParNode->_left = MinNode->_right;
					}
					delete MinNode;
					MinNode = nullptr;
				}
				return true;
			}
		}
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

	~BSTree()
	{
		_Destory(_root);
	}

	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);
	}

	//BSTree() // 这样写也行，但是下面是C++11的用法
	//{}
	BSTree() = default; // C++11的关键字，强制编译器生成默认的构造

	BSTree<K> operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

protected:
	Node* _Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* CopyRoot = new Node(root->_key); // 中序递归链接左右子树
		CopyRoot->_left = _Copy(root->_left);
		CopyRoot->_right = _Copy(root->_right);
		return CopyRoot;
	}

	void _Destory(Node*& root) // 加引用下面的置空就起作用了
	{
		if (root == nullptr)
		{
			return;
		}
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
		root = nullptr;
	}

	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (key < root->_key)
		{
			_FindR(root->_left, key);
		}
		else if (key > root->_key)
		{
			_FindR(root->_right, key);
		}
		else
		{
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (key < root->_key)
		{
			return _InsertR(root->_left, key);
		}
		else if (key > root->_key)
		{
			return _InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
	}

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else // 找到要删除的结点，开始删除
		{
			Node* del = root;
			if (root->_left == nullptr) // 这里就体现了引用的神之一手，根本不用判断父亲
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else // 找右树的最左节点替换删除
			{
				Node* MinNode = root->_right;
				while (MinNode->_left)
				{
					MinNode = MinNode->_left;
				}
				swap(root->_key, MinNode->_key);
				//return EraseR(key);  错的
				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	public:
		Node* _root = nullptr;
};

//二叉搜索树的KV结构
namespace KeyValue
{
	//定义两个类模板参数K、V
	template<class K, class V>
	class BSTreeNode
	{
	public:
		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}

		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key; //存放了两个类型的数据，相比较与K模型
		V _value;
	};

	//同样的，定义两个类模板参数K、V
	//搜索二叉树依旧是按照K的数据进行排序，和V无关
	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		//查找只和数据_key有关，与数据_value无关
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}

		//删除只和数据_key有关，与数据_value无关
		bool Erase(const K& key)
		{
			//... 和K模型一样
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	protected:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}

		Node* _root = nullptr;
	};

	void TestBSTree1()
	{
		BSTree<string, string> dict; // 字典树，如果所有单词都在里面就能很准确查找
		dict.Insert("sort", "排序");
		dict.Insert("left", "左边");
		dict.Insert("right", "右边");
		dict.Insert("string", "字符串");
		dict.Insert("insert", "插入");
		string str;
		while (cin >> str) // Crtl+z+换行结束，或者Crtl+c结束
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << "对应的中文:" << ret->_value << endl;
			}
			else
			{
				cout << "对应的中文->无此单词" << endl;
			}
		}
	}

	void TestBSTree2() // 统计水果出现的次数
	{
		string arr[] = { "香蕉", "苹果", "香蕉", "草莓", "香蕉", "苹果", "苹果", "苹果" };

		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			//BSTreeNode<string, int>* ret = countTree.Find(str);
			auto ret = countTree.Find(str);
			if (ret)
			{
				ret->_value++;
			}
			else
			{
				countTree.Insert(str, 1);
			}
		}
		countTree.InOrder();
	}
}